package com.tucc.hello.leetcode.no1601_2000.no1734;

import java.util.Stack;

/**
 *
 * @Description:
 * @Date: Created in ${DATE} ${HOUR}:${MINUTE}
 * @Author: tucc
 */
public class Solution {

    /**
     * 给你一个整数数组perm，它是前n个正整数的排列，且n是个 奇数。
     *
     * 它被加密成另一个长度为 n - 1的整数数组encoded，满足encoded[i] = perm[i] XOR perm[i + 1]。比方说，如果perm = [1,3,2]，那么encoded = [2,1]。
     *
     * 给你encoded数组，请你返回原始数组perm。题目保证答案存在且唯一。
     *
     * 
     *
     * 示例 1：
     *
     * 输入：encoded = [3,1]
     * 输出：[1,2,3]
     * 解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
     * 示例 2：
     *
     * 输入：encoded = [6,5,4,6]
     * 输出：[2,4,1,5,3]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/decode-xored-permutation
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param encoded
     * @return
     */
    public int[] decode(int[] encoded) {
        int[] origin = new int[encoded.length + 1];
        int fin = 1;
        for(int i = 2;i <= encoded.length + 1;i ++){
            fin ^= i;
        }
        for(int i = 1;i < encoded.length;i += 2){
            fin ^= encoded[i];
        }
        origin[0] = fin;
        for(int i = 1;i <= encoded.length;i ++){
            origin[i] = origin[i - 1] ^ encoded[i - 1];
        }
        return origin;
    }


    public int[] decode2(int[] encoded){
        int[] origin = null;
        int n = encoded.length + 1;
        int[] members = new int[n];
        for(int i = 0;i < n;i ++){
            members[i] = i + 1;
        }
        perm(members, new Stack<>(), encoded);
        if(result != null){
            origin = new int[result.length];
            for(int i = 0;i < result.length;i ++){
                origin[i] = result[i];
            }
        }
        return origin;
    }
    Integer[] result = null;
    public void perm(int[] array, Stack<Integer> stack, int[] encoded) {
        if(array.length <= 0) {
            result = stack.toArray(new Integer[0]);
        } else {
            for (int i = 0; i < array.length; i++) {
                int[] tempArray = new int[array.length-1];
                System.arraycopy(array,0,tempArray,0,i);
                System.arraycopy(array,i+1,tempArray,i,array.length-i-1);
                int size = stack.size();
                if(size >= 1){
                    int n = stack.get(size - 1);
                    if((array[i] ^ n) == encoded[size - 1]){
                        stack.push(array[i]);
                        perm(tempArray, stack, encoded);
                        stack.pop();
                    }
                }
                else {
                    stack.push(array[i]);
                    perm(tempArray, stack, encoded);
                    stack.pop();
                }
            }
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] result = solution.decode(new int[]{6,5,4,6});
        for(int i = 0;i < result.length;i ++) {
            System.out.print(result[i] + " ");
        }


    }

}
